package com.Questions.DP;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;
import java.util.Random;

import java.util.Collections;

/**
 * 求最大子数组和
 */
public class leetcode53 {
    // 除了分治 这里学习一下 动态规划算法
    // 算法思路
    // 使用f(i)代表第i个数结尾的[最大子数组和]
    // 那么答案就是f(i)的最大值即可
    // 问题是如何计算 f(i)
    // 动态规划转移方程f(i)=max(f(i-1)+nums[i],nums[i])
    // 解释说明 以i为结尾的最大和只有两种可能
    // 要么是前一个i-1 为结尾的最大和 要么是 i本身
    public int maxSubArray(int[] nums) {
        int pre=0,maxAns=nums[0];
        for(int x:nums){
            pre=Math.max(pre+x,x);
            maxAns=Math.max(maxAns,pre);
        }
        return maxAns;
    }
}
